package leetcode;

/**
 * @创建人 MBY381
 * @创建时间 2022/4/4 16:10
 * @描述 给你一个非负整数数组 nums ，你最初位于数组的第一个位置。
 * <p>
 * 数组中的每个元素代表你在该位置可以跳跃的最大长度。
 * <p>
 * 你的目标是使用最少的跳跃次数到达数组的最后一个位置。
 * <p>
 * 假设你总是可以到达数组的最后一个位置。
 */
public class Solution45 {
    /**
     * 傻杯解法
     *
     * @param nums 必定可到达终点
     * @return
     */
    public static int jump(int[] nums) {
        int steps = 0;
        int tag = 0, max = 0, len = nums.length, tag2;
        if (len <= 1) {
            return 0;
        }
        for (int i = 0; i < len; i++) {
            tag2 = tag + nums[tag] + 1;
            for (int j = tag; j <= i + nums[i]; j++) {
                if (j == len - 1) {
                    return steps + 1;
                }
                if ((nums[j] + j) > max) {
                    max = nums[j] + j;
                    tag = j;
                }
            }
            ++steps;
            i = tag - 1;
            if (tag + nums[tag] > len) {
                steps++;
                break;
            }
            max = 0;
        }
        return steps;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{2, 3, 0, 1, 4};
        System.out.println(jump(nums));
    }
}
